#include "SolutionList.h"
#include "Quicksort.h"

int n_value = 0, b_value = 0;

//Declaring the functions that we will use for retrieve all the solutions

list recoverSolution(list l, int* P, int KSolution, int* matrix, int* a, int* c);
list backtracking(list l, solution* stemp, int elementIndex, int* P, int KSolution, int* matrix, int* a, int* c);
list searchAlternativeSolution(int t, int j, int zcum, int j1, int i, list l, int* P, int KSolution, int* matrix, int* a, int* c);

int main(char* args, int argc)
{
	//Begin initialization

	/*
	n_value: number of items
	b_value: knapsack capacity	
	a_vector: weight values for every item
	c_vector: profit values for every item

	matrix: structure where to save all the results

	tempSolution: variable used for memorizing temporary solutions
	listResult: the list of the final solutions

	P: number of solutions founded
	*/

	//File reading variables
	int *a_vector, *c_vector;
	FILE *in;

	int r,s,m,i, z = 0;
	int *matrix;

	int trash = 0;	//Used for putting useless values

	//List creating variables
	solution tempSolution;
	list listResult = emptyList();
	int P = 0;

	//Computational time measuring variables
	clock_t begin, end;

	//START Reading from .in file
	in = fopen(TEST_IN, "r");
	if (in == NULL) 
		perror("\n!!NO FILE FOUNDED!!\n");
	fscanf(in,"%d\n",&n_value);

	//initialize the arrays
	a_vector = (int*) malloc(n_value*sizeof(int));
	c_vector = (int*) malloc(n_value*sizeof(int));

	for(i=0; i<n_value; i++)
	{
		fscanf(in,"%5d %5d %5d\n", &trash, &c_vector[i], &a_vector[i]);
	}
	fscanf(in,"%d\n",&b_value);

	fclose(in);

	printf("N=%i B=%i\n",n_value,b_value);
	//END Reading from .in file

	//START Order the arrays
	quickSort(a_vector,c_vector,n_value);
	if(VERBOSE)	//Print the ordered objects
		for(i=0; i<n_value; i++)
			printf("%i: Weight: %i \t Profit %i\n",i,a_vector[i],c_vector[i]);

	//END Order the arrays


	for(r=0; r<n_value; r++)
		trash += a_vector[r];

	printf("%i", trash);

	//We will simulate the matrix in this way
	//int offset = i * colums (number of colums in the matrix) + j;
	//now mat[offset] corresponds to m(i, j)
	//For memory efficient use (locality principle)

	//Memory allocation
	matrix = (int*) malloc(sizeof(int)*((b_value+1)*n_value));

	for(r=0; r <= b_value; r++)
	{
		for(s=0; s < n_value; s++)
		{
			if(r==0)
				matrix[r * n_value + s] = 0;
			else
				matrix[r * n_value + s] = -1;
		}
	}

	//Begin Forward Enumeration
	begin = clock();	//Start computation

	//Begin Initial ramification
	for(s=0; s < n_value; s++)
		matrix[a_vector[s]*n_value + s] = c_vector[s];	//inserting first values
	//End Initial ramification

	//Begin Ramification of supernodes
	for(r=a_vector[0]; r <= b_value - a_vector[0]; r++)
	{
		m = n_value;
		
		for(s=0; s < n_value; s++)
		{
			if(matrix[r*n_value + s] >= 0)
			{
				m = s;
				break;
			}
		}

		if(m != n_value)
		{
			z = matrix[r*n_value + m];
			for(s=m; s < n_value; s++)
			{
				if(r+a_vector[s] <= b_value)
				{
					if(matrix[r*n_value + s] > z)
						z = matrix[r*n_value + s];
					matrix[(r+a_vector[s])*n_value + s] = z + c_vector[s];
				}
			}
		}
	}
	//End Ramification of supernodes
	
	//Build initial best K list values
	for(r=b_value; r >= 0; r--)
	{
		for(s=n_value-1; s >= 0; s--)
		{
			if(matrix[r*n_value + s] == -1)	//if the value is not initialized, we skip it
				continue;

			else
			{
				if(P < K_VALUE)
				{
					tempSolution = initSolutionWithParameters(n_value,NULL, matrix[r*n_value + s], r, s, 0);
					listResult = insertInOrderSolution(listResult,tempSolution, &trash);

					P++;			//increasing the number of solution founded
					
					trash = 0;
				}
				else
				{
					if(matrix[r*n_value + s] > lastSolutionValue(listResult))
					{
						tempSolution = initSolutionWithParameters(n_value,NULL, matrix[r*n_value + s], r, s, 0);
						listResult = insertInOrderSolution(listResult,tempSolution, &trash);
						listResult = keepFirstNElements(listResult, K_VALUE);	//delete the last element
						
						trash = 0;
					}
				}
			}
		}
	}
	//End of building initial best K list values
	
	if(BACKTRACKING) //Recovering the solutions
		listResult = recoverSolution(listResult,&P,K_VALUE,matrix,a_vector,c_vector);
	//End recovering the solutions

	end = clock();	//End of computation
	//End Forward Enumeration

	//Print the resulted matrix
	if(VERBOSE)
	{
		for(r=0; r <= b_value; r++)
		{
			for(s=0; s < n_value; s++)
			{ 
				printf("%i\t", matrix[r*n_value + s]);
			}
			printf("\n");
		}
	}
	//Print computational time
	printf("Computational time: %f\n", difftime(end,begin)/CLOCKS_PER_SEC);

	printf("VERBOSE: %i\n", VERBOSE);
	printf("BACKTRACKING: %i\n", BACKTRACKING);
	printf("SEARCH_ALT_SOLUTIONS: %i\n", SEARCH_ALT_SOLUTIONS);

	if(VERBOSE)
		showList(listResult);
	else
		showListValue(listResult);

	free(a_vector);
	free(c_vector);
	free(matrix);

	return 0;
}

/*
*TO CHECK: IT SEEMS THAT ELEMENT AT RETURN A REFERENCE OF THE SOLUTION IN THE LIST
*IN THIS WAY MODIFIED ELEMENT IS USELESS BUT IT DOESNT UPDATE THE CONTROL VARIABLE
*/
list recoverSolution(list l, int* P, int KSolution, int* matrix, int* a, int* c)
{
	int i=0;
	solution stemp;
	while(i<*P)
	{
		if(elementAt(l,i).control == 0)
		{
			stemp = elementAt(l,i);	//Save the solution to modify in a temp variable solution
			l = backtracking(l,&stemp,i,P,KSolution,matrix,a,c);
			l = modifyElementAt(l,stemp,i);	//return the modified list with the element at index i modified
		}
		i++;
	}
	return l;
}

list backtracking(list l, solution* stemp, int elementIndex, int* P, int KSolution, int* matrix, int* a, int* c)
{
	int t = stemp->i;		//Solution row
	int j = stemp->j;		//Solution column
	int z = stemp->value;	//Objective function value
	int j1 = stemp->j;		//Original solution column (used in searchAlternativeSolution)		
	int temp;				//temp value

	int zcum = 0;

	while(t>0)
	{
		t -= a[j];
		z -= c[j];
		zcum += c[j];

		stemp->x[j] += 1;

		for(temp=j; temp>=0; temp--)
			if(matrix[t*n_value + temp] == z)
				break;

		j = temp;

		if(SEARCH_ALT_SOLUTIONS)	//search for alternative solution
			if(t>0)			
				l = searchAlternativeSolution(t,j,zcum,j1,elementIndex,l,P,KSolution, matrix, a, c);
		
		j1 = j;
	}

	stemp->control = 1; //the solution is setted!
	return l;
}

list searchAlternativeSolution(int t, int j, int zcum, int j1, int i, list l, int* P, int KSolution, int* matrix, int* a, int* c)
{
	int index;		//General index
	int s;		//From the first column to the column j1
	int g = 0;	//Index of the alternative solution
	solution stemp1, stemp2;	//temporary solutions that can be inserted in the final solution list 
	solution stempAtIndex = elementAt(l,i); //instead of calling always elementAt we will use the image of this solution

	for(s=0; s<=j1; s++)
	{
		if(s!=j)
		{
			if(matrix[t*n_value + s]>=0)	//valid solution
			{	
				if(matrix[t*n_value + s] + zcum >= lastSolutionValue(l))	//A NEW SOLUTION IS FOUND
				{	
					g=0;
					if(*P < KSolution)
						*P = *P + 1;
					stemp1 = initSolutionWithParameters(stempAtIndex.x_dim,NULL,matrix[t*n_value + s] + zcum,stempAtIndex.i,stempAtIndex.j,0);
					stemp2 = initSolutionWithParameters(stempAtIndex.x_dim,NULL,matrix[t*n_value + s],t,s,0);
					l = insertInOrderSolution(l,stemp1,&g);

					l = backtracking(l,&stemp2,g,P,KSolution,matrix,a,c);

					for(index=0; index<5; index++)
						stemp1.x[index] = stemp2.x[index] + stempAtIndex.x[index];

					stemp1.control = 1;	//The final solution is setted
					l = modifyElementAt(l,stemp1,g);	//update with the final solution
					l = keepFirstNElements(l,KSolution);	//Keep only the first K elements in the list
					
					if(stemp2.value >= lastSolutionValue(l))	//ANOTHER NEW SOLUTION IS FOUND
					{
						if(*P < KSolution)
							*P = *P + 1;
						l = insertInOrderSolution(l,stemp2,&g);
						l = keepFirstNElements(l,KSolution);	//Keep only the first K elements in the list
					}
					
				}
			}
		}
	}
	return l;
}